package com.ian.offer;

/**
 * @author zhangyaowen
 * @date 2021/3/1 11:35 下午
 */

/**
 * @author zhangyaowen
 * @date 2021/3/1 10:54 下午
 */

/**
 *
 * 统计一个数字在排序数组中出现的次数。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *  
 *
 * 限制：
 *
 * 0 <= 数组长度 <= 50000
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Search {

    public int search(int[] nums, int target) {

        if (nums.length ==0){
            return 0;
        }

        int mid =   bsearch(nums,0,nums.length-1,target);

        int l =mid, r = mid;
        int count = 0;

        while(l>=0){

            if (nums[l] ==target){
                count++;
            }else{
                break;
            }
            --l;
        }

        while(r<nums.length){
            if (nums[r] ==target){
                count++;
            }else{
                break;
            }
            ++r;

        }


        return count>0?count-1:0;
    }


    public int bsearch(int[] nums,int l,int r,int target){
        int mid = l+(r-l)>>>1;

        if (l>=r){
            return  l;
        }

        if (nums[mid] >target){
            return  bsearch(nums,0,mid,target);
        }else if (nums[mid]<target){
            return bsearch(nums,mid+1,r,target);
        }else{
            return  mid;
        }

    }


    public static void main(String[] args) {
        int[] nums = new int[]{1,4,4};
        int target = 4;

        Search search = new Search();

        System.out.println( search.search(nums,target));

    }
}

